Graphen

 Inhalt  English version  zurück
Knoten und Kanten
Def.: Ein (gerichteter) Graph ist ein Paar G = (V, E), hierbei ist V eine endliche Menge von Knoten und E  VV eine Relation auf V, die Menge der Kanten.
Darstellung von Graphen: Die Knoten werden als Punkte oder Kreise gezeichnet, die Kanten als Pfeile, wobei ein Pfeil vom Knoten u  V zum Knoten v  V zeigt, wenn (u, v)  E.
Beispiel: G = (V, E)   mit   V = {1, 2, 3, 4, 5}   und   E = {(1,2), (1,3), (4,1), (3,1), (2,3)}
Bild 1:  Darstellung des Graphen G
Def.: Sei G = (V, E) ein Graph und u  V ein Knoten. Ein Knoten v  V heißt direkt erreichbar von u, wenn es eine Kante von u nach v gibt, d.h. wenn (u, v)  E gilt.
Der Ausgangsgrad o(u) eines Knotens u ist gleich der Anzahl der Knoten v, die von u direkt erreichbar sind, d.h.
o(u)  =  | { v |  (u, v)  E } |
Der Eingangsgrad i(u) eines Knotens u ist gleich der Anzahl der Knoten v, von denen er direkt erreichbar ist, d.h.
 i(u)  =   | { v |  (v, u)  E } |
Ein Knoten u heißt isoliert wenn  o(u) = i(u) = 0  gilt.
Beispiel: In G ist Knoten 1 von Knoten 4 direkt erreichbar; Knoten 3 hat den Ausgangsgrad 1 und den Eingangsgrad 2. Knoten 5 ist isoliert.
Pfad
Def.: Ein Pfad in einem Graphen ist eine endliche Folge von Kanten
p    =    (u1, v1), ..., (um, vm)
mit   m  0   und   vi = ui+1   für alle   i  {1, ..., m-1}.
m ist die Länge des Pfades. Wir identifizieren Kanten und Pfade der Länge 1. Der Pfad der Länge 0 heißt der leere Pfad. Der Knoten u1 heißt Anfangsknoten von p, der Knoten vm heißt Endknoten. Alle anderen Knoten von p heißen innere Knoten.
Beispiel: p1 = (4,1), (1,3), (3,1), (1,3)
p2 = (1,2), (2,3), (3,1)
p3 = (4,1)
p4 = (4,1), (1,2), (2,3), (3,1)     sind Pfade in obigem Graphen G.
Der Pfad p1 hat die Länge 4, der Pfad p3 hat die Länge 1. Im Pfad p2 ist der Knoten 1 zugleich Anfangs- und Endknoten. In p4 ist Knoten 1 sowohl innerer Knoten als auch Endknoten.
Def.: Sei  p  =  (u1, v1), ..., (um, vm)   ein Pfad in einem Graphen G.
p heißt einfach, wenn er keine Kante mehrfach durchläuft, d.h. wenn alle (ui, vi) paarweise verschieden sind (i = 1, ..., m).
p heißt Zyklus, wenn er geschlossen ist, d.h. wenn  vm = u1  gilt.
p heißt Weg, wenn er keinen Knoten mehrfach durchläuft, d.h. wenn alle ui untereinander und alle vj untereinander paarweise verschieden sind (i, j = 1, ..., m).
p heißt Kreis, wenn er ein Weg ist und geschlossen ist, d.h. ein Zyklus ist.
Beispiel: Der Pfad p1 aus dem vorigen Beispiel ist kein einfacher Pfad, weil er die Kante (1,3) zweimal enthält. Der Pfad p4 ist ein einfacher Pfad, aber kein Weg, weil er den Knoten 1 mehrmals durchläuft. Der Pfad p2 ist ein Zyklus und sogar ein Kreis.
Satz: Sei G = (V, E) ein Graph mit n Knoten, d.h. |V|  =  n. Dann hat jeder Weg in G höchstens die Länge n.
Beweis: Sei   p  =  (u1, v1), ..., (um, vm)   ein Pfad der Länge m > n. Dann können nicht alle ui verschieden sein, da es nur n Knoten gibt. Also ist p kein Weg.
Satz: Wenn es in G einen Pfad von u nach v gibt, dann gibt es auch einen Weg von u nach v.
Beweis: Sei   p  =  (u1, v1), ..., (um, vm)   ein Pfad von u nach v. Aus p wird wie folgt ein Weg konstruiert:
Solange p kein Weg ist wiederhole:
a)  Suche einen Knoten w, der in p zweimal vorkommt, d.h. w = ui und w = vj mit i  j
b)  Streiche das Stück von ui nach vj in p, d.h. setze
      p  =  (u1, v1), ..., (ui-1, vi-1), (uj+1, vj+1), ..., (um, vm)
Im folgenden Bild 2 ist ein Pfad dargestellt, der einen Knoten ui = vj zweimal durchläuft. Indem das rot dargestellte Stück von ui nach vj entfernt wird, entsteht ein Weg.
Bild 2:  Pfad, der einen Knoten zweimal durchläuft
Baum
Def.: Ein gerichteter Graph T = (V, E) ist ein Baum, wenn
-   er keine Zyklen enthält
-   er genau einen Knoten mit Eingangsgrad 0 enthält; dieser Knoten ist die Wurzel des Baumes
-   alle anderen Knoten den Eingangsgrad 1 haben
Def.: Sei T ein Baum mit Wurzel r. Ein Knoten v heißt direkter Nachfolger eines Knotens u, wenn es eine Kante von u nach v gibt. Ein Knoten w heißt Nachfolger von u, wenn es einen nichtleeren Pfad von u nach w gibt.
Ein Knoten b heißt Blatt, wenn er keine Nachfolger hat; alle anderen Knoten heißen innere Knoten des Baumes.
Die Tiefe d(v) eines Knotens v ist die Länge des Weges von der Wurzel r nach v. Die Tiefe d(T) des Baumes ist die maximale Tiefe der Knoten.
Def.: Ein Baum T ist ein binärer Baum, wenn jeder Knoten einen Ausgangsgrad von höchstens 2 hat.
Ein binärer Baum heißt vollständig, wenn
-   jedes Blatt die Tiefe d(T) oder d(T)-1 hat
-   jeder Knoten mit Ausgangsgrad 1 die Tiefe d(T)-1 hat.
Ein vollständiger binärer Baum T mit n Knoten hat eine Tiefe von d(T))  =  int(log(n)).
Vollständiger binärer Baum
Bild 3:  Vollständiger binärer Baum mit 11 Knoten
Ungerichtete Graphen
Ein ungerichteter Graph lässt sich als Spezialfall eines gerichteten Graphen auffassen, nämlich als ein gerichteter Graph, bei dem die Kanten stets in beide Richtungen verlaufen. Dann können die Richtungsangaben auch weggelassen werden.
Def.: Ein gerichteter Graph G = (V, E) ist ein ungerichteter Graph, wenn seine Kantenrelation E symmetrisch ist, d.h. wenn gilt:
E = E -1
Ein Graph ist also ungerichtet, wenn für alle Kanten (u, v) gilt: (v, u) ist ebenfalls Kante.
Bild 4:  Ungerichteter Graph
Def.: Sei G = (V, E) ein ungerichteter Graph.
G heißt zusammenhängend, wenn es in G von jedem Knoten zu jedem anderen Knoten mindestens einen Weg gibt.
G heißt kreisfrei, wenn es in G von jedem Knoten zu jedem anderen Knoten höchstens einen Weg gibt.
G ist ein Baum, wenn G zusammenhängend und kreisfrei ist, d.h. wenn es in G von jedem Knoten zu jedem anderen Knoten genau einen Weg gibt.
Def.: Sei G = (V, E) ein ungerichteter Graph. Ein Graph G ' = (V ', E ') heißt Teilgraph von G, wenn er aus gewissen Knoten von G und Kanten von G zwischen diesen Knoten besteht und wenn er ungerichtet ist, d.h. wenn gilt
V '  V
E '  E    V 'V '     und
E ' =  E ' -1
zurück
homePage maintained by lang@fh-flensburg.de. Created: 29.01.1998 Updated: 07.01.2002